package com.future;

/**
 * Description: 1139. ������ 1 Ϊ�߽��������
 * ����һ�������� 0 �� 1 ��ɵĶ�ά����?grid�������ҳ��߽�ȫ���� 1 ��ɵ���� ������ �����񣬲����ظ��������е�Ԫ����������������ڣ��򷵻� 0��
 * <p>
 * ?
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺grid = [[1,1,1],[1,0,1],[1,1,1]]
 * �����9
 * ʾ�� 2��
 * <p>
 * ���룺grid = [[1,1,0,0]]
 * �����1
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/largest-1-bordered-square
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/4/14 09:17
 */
public class Solution_1139 {

    public static void main(String[] args) {
        int[][] grid = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        grid = new int[][]{
                {1, 1, 1, 1, 1, 0},
                {1, 0, 0, 1, 0, 1},
                {1, 0, 1, 1, 0, 1},
                {0, 1, 1, 1, 1, 1}};
       /* grid = new int[][]{
                {0, 1, 1, 1, 1, 1, 1, 0},
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 1, 1, 1, 0, 1, 1},
                {1, 1, 1, 1, 0, 1, 1, 1},
                {1, 0, 1, 0, 0, 1, 1, 1},
                {0, 1, 1, 1, 1, 0, 1, 1}
        };*/
        // grid = new int[][]{{0, 0, 0, 1}};
        System.out.println(largest1BorderedSquare(grid));
    }

    public static int largest1BorderedSquare(int[][] grid) {
        /**
         * right,�����ҵ�������1�ĸ���������0���´�0����
         */
        int[][] right = new int[grid.length][grid[0].length];
        /**
         * down,�����µ�������1�ĸ���������0���´�0����
         */
        int[][] down = new int[grid.length][grid[0].length];
        setBorderMap(grid, right, down);
        int ans = 0;
        int R = grid.length;
        int C = grid[0].length;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                int border = Math.min(right[i][j], down[i][j]);
                /**
                 * ����
                 * (i , j)  (i,i_r)
                 * (j_l,j)  (j_l,i_r)
                 * �ĸ�����
                 */
                while (border != 0) {
                    int i_r = j + border - 1;
                    int j_l = i + border - 1;
                    if (j_l >= grid.length || i_r >= grid[0].length) {
                        continue;
                    }
                    if (down[i][i_r] >= border && right[j_l][j] >= border) {
                        ans = Math.max(ans, border * border);
                    }
                    border--;
                }

            }
        }
        return ans;
    }


    /**
     * m =
     * {1   1   1}
     * {1   0   1}
     * {1   1   1}
     * right��������������㣬����������1���ۼӣ�����0�����¼���
     * �� right=
     * {3   2   1}
     * {1   0   1}
     * {3   2   1}
     * down�����������ϼ��㣬����������1���ۼӣ�����0�����¼���
     * �� down=
     * {3   1   3}
     * {2   0   2}
     * {1   1   1}
     */
    public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
        // ��
        int r = m.length;
        // ��
        int c = m[0].length;
        for (int i = 0; i < r; i++) {
            right[i][c - 1] = m[i][c - 1];
            for (int j = c - 2; j >= 0; j--) {
                int val = m[i][j];
                right[i][j] = val == 0 ? 0 : right[i][j + 1] + val;
            }
        }
        for (int i = 0; i < c; i++) {
            down[r - 1][i] = m[r - 1][i];
            for (int j = r - 2; j >= 0; j--) {
                int val = m[j][i];
                down[j][i] = val == 0 ? 0 : val + down[j + 1][i];
            }
        }

    }
}
